//
// Created by LiuYou on 2021/11/29.
//

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>


/**
* 最简单的排序实现
*
* 当i = 1, j = 8时，虽然把2排到前面了，但是也把3排到了最后，效率非常低
*/
static void bubbleSort1(std::vector<int>& arr) {

    int sumSwap = 0, sumIn = 0, sumOut = 0;
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[i] > arr[j]) {
                std::swap( arr[i], arr[j] );
                sumSwap++;
            }
            sumIn++;
        }
        sumOut++;
    }
    std::cout << "sort1执行次数：sumSwap:" << sumSwap << " sumIn:" << sumIn << " sumOut:" << sumOut << std::endl;
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    std::cout << std::endl;
}

/**
 * 冒泡排序，从底往上遍历
 *
 * 当i=2时，把4往前排了，还把3往前排了，最终把2排到第二位
 */
static void bubbleSort2(std::vector<int>& arr) {
    int sumSwap = 0, sumIn = 0, sumOut = 0;
    for (int i = 0; i < arr.size(); i++) {
        for (int j = arr.size() - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {
                std::swap( arr[j - 1], arr[j] );
                sumSwap++;
            }
            sumIn++;
        }
        sumOut++;
    }
    std::cout << "sort2执行次数：sumSwap:" << sumSwap << " sumIn:" << sumIn << " sumOut:" << sumOut << std::endl;
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    std::cout << std::endl;
}

/**
 * 冒泡排序优化，避免了已经是有序的情况下的无意义的循环
 *
 * 9, 1, 5, 8, 3, 7, 4, 6, 2
 *
 * 2, 1, 3, 4, 5, 6, 7, 8, 9 这种情况下，只需要把2和1交换
 */
static void bubbleSort3(std::vector<int>& arr) {
    int sumSwap = 0, sumIn = 0, sumOut = 0;
    bool flag = true;
    for (int i = 0; i < arr.size() && flag; i++) {// i < arr.length && flag
        flag = false;
        for (int j = arr.size() - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {// 数组是否有序
                std::swap( arr[j - 1], arr[j] );
                flag = true;// 交换后，再判断
                sumSwap++;
            }
            sumIn++;
        }
        sumOut++;
    }
    std::cout << "sort3执行次数：sumSwap:" << sumSwap << " sumIn:" << sumIn << " sumOut:" << sumOut << std::endl;
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    std::cout << std::endl;
}


/*
 * 这个 BubbleSort2.cpp 文件不用看了。
 */
int main(int argc, char** argv) {
    {
        std::vector<int> arr{3, 2, 5, 4, 1};
        bubbleSort1( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }


    return 0;
}

